package com.heima.algorithm.sort;

/**
 * <strong>选择排序</strong>
 * <p>思想：每次从未排序区间选择最大的元素放到未排序区间的末尾，未排序区间减1，然后继续选择最大元素放到未排序区间末尾，直到未排序区间长度为1</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/28 13:22
 */
public class SelectionSort {
    //（1）基于比较的排序算法
    //（2）最好情况：O(n^2)，最坏情况：O(n^2)，平均情况：O(n^2)，空间复杂度：O(1)，稳定：否，思想：比较
    //（3）交换次数一般少于冒泡

    /**
     * 选择排序
     * @param arr 待排序数组
     */
    public static void selectionSort(int[] arr) {
        // 选择排序，每次从当前未排序区间中选择最大的元素，放到未排序区间的最右边，rightBound为当前未排序区间的右边界（包含）
        for (int rightBound = arr.length - 1; rightBound > 0; rightBound--){
            // 当前未排序区间中最大元素的索引，初始化为右边界索引，默认最后一个就是最大元素
            int maxIndex = rightBound;
            // 遍历有边界左侧的所有元素，寻找当前未排序区间中的最大元素
            for (int i = 0; i < rightBound; i++){
                if (arr[i] > arr[maxIndex]){
                    maxIndex = i;
                }
            }
            // 在边界左侧找到最大值则交换最大元素的索引和右边界元素的索引
            if (maxIndex != rightBound) {
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[rightBound];
                arr[rightBound] = temp;
            }
        }
    }
}
